﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Recursives
{
    class HanoiTest
    {
        public static void Hanoi(int n, string source, string middle, string target)
        {
            if (n == 1)
            {
                Console.WriteLine(String.Format("{0}->{1}", source, target));
            }
            else
            {
                Hanoi(n - 1, source, target, middle);
                Console.WriteLine(String.Format("{0}->{1}", source, target));
                Hanoi(n - 1, middle, source, target);
            }
        }

        public static void Hanoi2(int n, string source, string middle, string target)
        {
            var stack = new Stack<StackFrame>();
            var currentAddress = 1;

            while (true)
            {
                switch (currentAddress)
                {
                    case 1:
                        {
                            stack.Push(new StackFrame
                            {
                                N = n,
                                Source = source,
                                Middle = middle,
                                Target = target,
                                ReturnAddress = 5
                            });
                            currentAddress = 2;
                        }
                        break;
                    case 2:
                        {
                            var frame = stack.Peek();
                            if (frame.N == 1)
                            {
                                Console.WriteLine(String.Format("{0}->{1}", frame.Source, frame.Target));
                                currentAddress = 4;
                            }
                            else
                            {
                                stack.Push(new StackFrame
                                {
                                    N = frame.N - 1,
                                    Source = frame.Source,
                                    Middle = frame.Target,
                                    Target = frame.Middle,
                                    ReturnAddress = 3
                                });
                                currentAddress = 2;
                            }
                        }
                        break;
                    case 3:
                        {
                            var frame = stack.Peek();
                            Console.WriteLine(String.Format("{0}->{1}", frame.Source, frame.Target));
                            stack.Push(new StackFrame
                            {
                                N = frame.N - 1,
                                Source = frame.Middle,
                                Middle = frame.Source,
                                Target = frame.Target,
                                ReturnAddress = 4
                            });
                            currentAddress = 2;
                        }
                        break;
                    case 4:
                        currentAddress = stack.Pop().ReturnAddress;
                        break;
                    case 5:
                        return;
                }
            }
        }

        private class StackFrame
        {
            public int N;
            public string Source;
            public string Middle;
            public string Target;
            public int ReturnAddress;
        }
    }
}
